package 左哥算法.ch06二叉树.树形dp;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class 最大搜索二叉子树 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Map<Integer, Tree> map = new HashMap<>();
        int n = sc.nextInt();
        Tree root = new Tree(sc.nextInt());
        map.put(root.val, root);
        while (n-- > 0) {
            int val = sc.nextInt();
            Tree cur = map.computeIfAbsent(val, Tree::new);
            int left = sc.nextInt();
            int right = sc.nextInt();
            if (left != 0) {
                cur.left = map.computeIfAbsent(left, Tree::new);
            }
            if (right != 0) {
                cur.right = map.computeIfAbsent(right, Tree::new);
            }
        }
        Info info = fun(root);
        System.out.println(info.size);
    }

    /**
     * 返回这棵树的Info信息
     *
     * @param tree
     * @return
     */
    public static Info fun(Tree tree) {
        if (tree == null) {
            return null;
        }
        Info info = new Info(tree.val);
        Info left = fun(tree.left);
        if (left != null) {
            if (!left.isSbt || left.max > tree.val) {
                info.isSbt = false;
            }
            info.min = Math.min(info.min, left.min);
            info.max = Math.max(info.max, left.max);
        }

        Info right = fun(tree.right);
        if (right != null) {
            if (!right.isSbt || right.min < tree.val) {
                info.isSbt = false;
            }
            info.min = Math.min(info.min, right.min);
            info.max = Math.max(info.max, right.max);
        }
        if (info.isSbt) {
            info.size += (left != null ? left.size : 0) + (right != null ? right.size : 0);
        } else {
            if (left != null) {
                info.size = Math.max(left.size, info.size);
            }
            if (right != null) {
                info.size = Math.max(right.size, info.size);
            }
        }
        return info;
    }

    public static class Info {
        int max;
        int min;
        boolean isSbt = true;
        public int size = 1; //默认就是1

        public Info(int val) {
            this.max = val;
            this.min = val;
        }
    }

    static class Tree {
        int val;
        Tree left;
        Tree right;

        public Tree(int val, Tree left, Tree right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        public Tree() {
        }

        public Tree(int val) {
            this.val = val;
        }
    }
}
